НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №1 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Складність алгоритму» Варіант № 20 Дата «17» квітня 2022  Мета роботи: Метою лабораторної роботи є отримання практичних навичок визначати часову складність алгоритму. Навчитися будувати алгоритми з мінімальною часовою складністю для вирішення поставлених задач. Завдання до лабораторної роботи Сформувати двовимірний масив цілих чисел, використовуючи датчик випадкових чисел. Використати оголошення масиву на n елементів (кількість елементів задавати з екрану). Провести оцінку часової складності алгоритму, використовуючи О-символіку в найгіршому або/і в середньому. Порівняти час роботи та кількість ітерацій/кількість кроків роботи програми з різною розмірністю масиву (10x10, 50x50, 100x100, 500x500). Оцінку часу роботи навести у вигляді графіка, або таблиці. Завдання відповідно до варіанту Завдання 1: В кожному рядку масиву всі від’ємні елементи перенести в ліву частину Завдання 2: В кожному стовпчику кожен третій елемент знищити, змістивши на його місце нижні елементи. Теоретичні відомості Алгоритм – це скінченна послідовність команд, які треба виконати над вхідними даними для отримання результату. Складність алгоритму – це кількісна характеристика, що відображує споживані алгоритмом ресурси під час свого виконання. Основними ресурсами, що оцінюються, є час виконання і простір пам’яті. Основними мірами обчислювальною складності алгоритмів є: часова складність, яка характеризує час, необхідний для виконання алгоритму на даній машині; цей час, як правило, визначається кількістю операцій, які потрібно виконати для реалізації алгоритму; ємнісна складність, яка характеризує пам’ять, необхідну для виконання алгоритму. Часова та ємнісна складність тісно пов’язані між собою. Обидві є функціями від розміру вхідних даних. В алгоритму є вхід - опис завдання, яке потрібно вирішити. На його розв’язання алгоритм витрачає певний час (тобто кількість операцій). Складність - це функція від довжини входу, значення якої дорівнює максимальному (за будь-якими входами даної довжини) кількості операцій, необхідних алгоритму для отримання відповіді. Одним зі спрощених видів аналізу складності алгоритмів, що використовують при комп’ютерній їх реалізації, є асимптотичний аналіз алгоритмів. Він використовується з метою порівняння витрат часу та інших ресурсів різноманітними алгоритмами, призначеними для вирішення одного і того самого завдання. Зазвичай алгоритм, більш ефективний в асимптотичному сенсі, буде більш продуктивним для всіх вхідних даних, за винятком дуже маленьких.  Результати роботи для завдання 1 Написано програмний код, що виконує зсуву всіх від’ємних елементів кожного рядка двовимірного масиву в ліву частину. Для цього спочатку з консолі вводиться розмір масиву, після цього масив заповнюється генератором випадкових чисел та виводиться на екран. Далі масив перетворюється, виводиться час роботи алгоритму та масив в результаті обробки. Алгоритм реалізовано за допомогою двох вкладених циклів, що завжди ітеруються від 0 до розміру масиву, тому складність алгоритму: N*N = O(N2)  / Рисунок 1. Залежність часу виконання від розмірів масиву / Рисунок 2. Скріншот результату завдання 1 Результати роботи для завдання 2 Написано програмний код, що виконує видалення кожного третього елемента в кожному стовпчику та зсуву всіх наступних вгору. Спочатку з консолі вводиться розмір масиву, після цього масив заповнюється генератором випадкових чисел та виводиться на екран. Далі масив перетворюється, виводиться час роботи алгоритму та масив в результаті обробки. Так як відбувається взаємодія лише з рядками і немає потреби ітеруватись по горизонталі, алгоритм можна реалізувати лінійним алгоритмом O(n). Для виконання завдання відбувається створення нового масиву з меншою кількістю рядків та перезапис ...